home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 42 / Amiga Format AFCD42 (Issue 126, Aug 1999).iso / -serious- / programming / other / jikes / src / set.h < prev    next >
C/C++ Source or Header  |  1999-05-14  |  15KB  |  613 lines
  1. // $Id: set.h,v 1.3 1999/01/25 20:00:31 shields Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1998, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #ifndef set_INCLUDED
  11. #define set_INCLUDED
  12.  
  13. #include "config.h"
  14. #include "assert.h"
  15. #include "symbol.h"
  16.  
  17. class ShadowSymbol
  18. { 
  19. public:
  20.     ShadowSymbol *next;
  21.     Symbol *symbol;
  22.     int pool_index;
  23.  
  24.     inline NameSymbol *Identity() { return symbol -> Identity(); }
  25.  
  26.     ShadowSymbol(Symbol *symbol_) : symbol(symbol_),
  27.                                     conflict(NULL)
  28.     {}
  29.  
  30.     ~ShadowSymbol() { delete conflict; }
  31.  
  32.     Symbol *Conflict(int i) { return (*conflict)[i]; }
  33.  
  34.     inline int NumConflicts()
  35.     {
  36.         return (conflict ? conflict -> Length() : 0);
  37.     }
  38.  
  39.     inline void AddConflict(Symbol *conflict_symbol)
  40.     {
  41.         if ((symbol != conflict_symbol) && (! Find(conflict_symbol)))
  42.             conflict -> Next() = conflict_symbol;
  43.         return;
  44.     }    
  45.  
  46.     inline void RemoveConflict(int k)
  47.     {
  48.         int last_index = conflict -> Length() - 1;
  49.         if (k < 0) // when k is negative, it identifies the main symbol
  50.              symbol = (*conflict)[last_index];
  51.         else (*conflict)[k] = (*conflict)[last_index];
  52.         conflict -> Reset(last_index);
  53.     }
  54.  
  55. private:
  56.     Tuple<Symbol *> *conflict;
  57.  
  58.     bool Find(Symbol *conflict_symbol)
  59.     {
  60.         if (! conflict)
  61.             conflict = new Tuple<Symbol *>(4);
  62.         for (int k = 0; k < conflict -> Length(); k++)
  63.             if ((*conflict)[k] == conflict_symbol)
  64.                 return true;
  65.         return false;
  66.     }    
  67. };
  68.  
  69.  
  70. class SymbolSet
  71. {
  72. public:
  73.     enum
  74.     {
  75.         DEFAULT_HASH_SIZE = 13,
  76.         MAX_HASH_SIZE = 1021
  77.     };
  78.  
  79.     SymbolSet(int hash_size_ = DEFAULT_HASH_SIZE) : symbol_pool(256),
  80.                                                     main_index(0),
  81.                                                     sub_index(0)
  82.     {
  83.         hash_size = (hash_size_ <= 0 ? 1 : hash_size_);
  84.  
  85.         prime_index = -1;
  86.         do
  87.         {
  88.             if (hash_size < primes[prime_index + 1])
  89.                 break;
  90.             prime_index++;
  91.         } while (primes[prime_index] < MAX_HASH_SIZE);
  92.  
  93.         base = (ShadowSymbol **) memset(new ShadowSymbol *[hash_size], 0, hash_size * sizeof(ShadowSymbol *));
  94.     }
  95.  
  96.     ~SymbolSet();
  97.  
  98.     //
  99.     // Calculate the size of the set an return the value.
  100.     //
  101.     inline int Size()
  102.     {
  103.         int size = 0;
  104.  
  105.         for (int i = 0; i < symbol_pool.Length(); i++)
  106.         {
  107.             ShadowSymbol *shadow = symbol_pool[i];
  108.             Symbol *symbol = shadow -> symbol;
  109.             for (int k = 0; symbol; symbol = (Symbol *) (k < shadow -> NumConflicts() ? shadow -> Conflict(k++) : NULL))
  110.                 size++;
  111.         }
  112.  
  113.         return size;
  114.     }
  115.  
  116.     //
  117.     // Empty out the set in question - i.e., remove all its elements
  118.     //
  119.     inline void SetEmpty()
  120.     {
  121.         for (int i = 0; i < symbol_pool.Length(); i++)
  122.             delete symbol_pool[i];
  123.         symbol_pool.Reset();
  124.         base = (ShadowSymbol **) memset(base, 0, hash_size * sizeof(ShadowSymbol *));
  125.     }
  126.  
  127.     //
  128.     // Empty out the set in question - i.e., remove all its elements
  129.     //
  130.     bool IsEmpty() { return symbol_pool.Length() == 0; }
  131.  
  132.     //
  133.     // Assignment of a set to another.
  134.     //
  135.     SymbolSet &operator=(SymbolSet &rhs)
  136.     {
  137.         if (this != &rhs)
  138.         {
  139.             this -> SetEmpty();
  140.             this -> Union(rhs);
  141.         }
  142.  
  143.         return *this;
  144.     }
  145.  
  146.     //
  147.     // Equality comparison of two sets
  148.     //
  149.     bool operator==(SymbolSet &);
  150.  
  151.     //
  152.     // NonEquality comparison of two sets
  153.     //
  154.     inline bool operator!=(SymbolSet &rhs)
  155.     {
  156.         return ! (*this == rhs);
  157.     }
  158.  
  159.     //
  160.     // Union the set in question with the set passed as argument: "set"
  161.     //
  162.     void Union(SymbolSet &);
  163.  
  164.     //
  165.     // Intersect the set in question with the set passed as argument: "set"
  166.     //
  167.     void Intersection(SymbolSet &);
  168.  
  169.     //
  170.     // Return a bolean value indicating whether or not the set in question intersects the set passed as argument: "set"
  171.     // i.e., is there at least one element of set that is also an element of "this" set.
  172.     //
  173.     bool Intersects(SymbolSet &);
  174.  
  175.     //
  176.     // How many elements with this name symbol do we have?
  177.     //
  178.     inline int NameCount(Symbol *element)
  179.     {
  180.         NameSymbol *name_symbol = element -> Identity();
  181.         for (ShadowSymbol *shadow = base[name_symbol -> index % hash_size]; shadow; shadow = shadow -> next)
  182.         {
  183.             if (shadow -> Identity() == name_symbol)
  184.                 return shadow -> NumConflicts() + 1;
  185.         }
  186.  
  187.         return 0;
  188.     }
  189.  
  190.     //
  191.     // Is "element" an element of the set in question ?
  192.     //
  193.     inline bool IsElement(Symbol *element)
  194.     {
  195. assert(element);
  196.         NameSymbol *name_symbol = element -> Identity();
  197.         for (ShadowSymbol *shadow = base[name_symbol -> index % hash_size]; shadow; shadow = shadow -> next)
  198.         {
  199.             if (shadow -> Identity() == name_symbol)
  200.             {
  201.                 Symbol *symbol = shadow -> symbol;
  202.                 for (int k = 0; symbol; symbol = (Symbol *) (k < shadow -> NumConflicts() ? shadow -> Conflict(k++) : NULL))
  203.                 {
  204.                     if (symbol == element)
  205.                         return true;
  206.                 }
  207.  
  208.                 return false;
  209.             }
  210.         }
  211.  
  212.         return false;
  213.     }
  214.  
  215.     //
  216.     // Add element to the set in question if was not already there.
  217.     //
  218.     inline void AddElement(Symbol *element)
  219.     {
  220.         NameSymbol *name_symbol = element -> Identity();
  221.         int i = name_symbol -> index % hash_size;
  222.  
  223.         ShadowSymbol *shadow;
  224.         for (shadow = base[i]; shadow; shadow = shadow -> next)
  225.         {
  226.             if (shadow -> Identity() == name_symbol)
  227.             {
  228.                 shadow -> AddConflict(element);
  229.                 return;
  230.             }
  231.         }
  232.  
  233.         shadow = new ShadowSymbol(element);
  234.         shadow -> pool_index = symbol_pool.Length();
  235.         symbol_pool.Next() = shadow;
  236.  
  237.         shadow -> next = base[i];
  238.         base[i] = shadow;
  239.  
  240.         //
  241.         // If the set is "adjustable" and the number of unique elements in it exceeds
  242.         // 2 times the size of the base, and we have not yet reached the maximum
  243.         // allowable size for a base, reallocate a larger base and rehash the elements.
  244.         //
  245.         if ((hash_size < MAX_HASH_SIZE) && (symbol_pool.Length() > (hash_size << 1)))
  246.             Rehash();
  247.  
  248.         return;
  249.     }
  250.  
  251.  
  252.     void RemoveElement(Symbol *);
  253.  
  254.     Symbol* FirstElement()
  255.     {
  256.         main_index = 0;
  257.         sub_index = 0;
  258.         return (main_index < symbol_pool.Length() ? symbol_pool[main_index] -> symbol : (Symbol *) NULL);
  259.     }
  260.  
  261.     Symbol* NextElement()
  262.     {
  263.         Symbol *symbol = NULL;
  264.  
  265.         if (main_index < symbol_pool.Length())
  266.         {
  267.              if (sub_index < symbol_pool[main_index] -> NumConflicts())
  268.                   symbol = symbol_pool[main_index] -> Conflict(sub_index++);
  269.              else
  270.              {
  271.                  main_index++;
  272.                  sub_index = 0;
  273.                  symbol = (main_index < symbol_pool.Length() ? symbol_pool[main_index] -> symbol : (Symbol *) NULL);
  274.              }
  275.         }
  276.  
  277.         return symbol;
  278.     }
  279.  
  280. protected:
  281.  
  282.     Tuple<ShadowSymbol *> symbol_pool;
  283.  
  284.     int main_index,
  285.         sub_index;
  286.  
  287.     ShadowSymbol **base;
  288.     int hash_size;
  289.  
  290.     static int primes[];
  291.     int prime_index;
  292.  
  293.     void Rehash();
  294. };
  295.  
  296.  
  297. //
  298. // Single-value Mapping from a name_symbol into a symbol with that name.
  299. //
  300. class SymbolMap : public SymbolSet
  301. {
  302. public:
  303.     SymbolMap(int hash_size_ = DEFAULT_HASH_SIZE) : SymbolSet(hash_size_)
  304.     {}
  305.  
  306.     //
  307.     // Is there an element with this name in the map ?
  308.     //
  309.     inline Symbol *Image(NameSymbol *name_symbol)
  310.     {
  311. assert(name_symbol);
  312.         for (ShadowSymbol *shadow = base[name_symbol -> index % hash_size]; shadow; shadow = shadow -> n